#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;


// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
 
class Solution {
public:
    void reorderList(ListNode* head) {
        stack<ListNode*> T;
        ListNode* i = head;
        ListNode* t = head;
        int j = 0;
        if (head == nullptr) {
            return;
        }
        while (i != nullptr) {
            T.push(i);
            j = j + 1;
            i = i->next;
        }
        int v = 1;
        int k = 0;
        while (v + k <j && t->next!=nullptr) {

             ListNode* temp= t->next;
             ListNode* wamp = T.top();
             if (temp != wamp) {
                 T.pop();
                 t->next = wamp;
                 wamp->next = temp;
             }
             t = temp;
             v = v + 1;
             k = k + 1;

        }
        t->next = nullptr;
        
        

    }
};



//int main() {
//    ListNode p1(1);
//    ListNode p2(2);
//    ListNode p3(3);
//    ListNode p4(4);
//    ListNode p5(5);
//    
//        
//    p1.next = &p2;
//    p2.next = &p3;
//    p3.next = &p4;
//    p4.next = &p5;
//    Solution S;
//    S.reorderList(&p1);
//    ListNode* i = &p1;
//    while (i != nullptr) {
//        cout << i->val << endl;
//        i = i->next;
//    }
//}